import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 手动实现一个插入排序算法：并测算处理80000个排序，需要花费多少时间?  本人电脑：1秒
 *
 * 弊端：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响
 * 解决办法：希尔算法
 */
public class InsertSortDemo {
    public static void main(String[] args) {
        int[] ints = {101, 34, 119, 1,-1,5,-6};
        System.out.println("排序前数组：");
        System.out.println(Arrays.toString(ints));
        insertSort(ints);
        System.out.println("排序后数组：");
        System.out.println(Arrays.toString(ints));
        System.out.println("-----------------------");

        //测试插入排序的时间复杂度
        //若处理80000个排序，需要花费多少时间? 本人电脑花费：1秒
        insertSortTest();
    }

    //测试插入排序的时间复杂度
    //测试算法：若处理80000个排序，需要花费多少时间? 本人电脑：1秒
    public static void insertSortTest(){
        int[] arr = new int[80000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间："+s1);
        //进行排序
        insertSort(arr);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间："+s2);
    }

    //插入排序算法
    public static void insertSort(int[] arr){
        //先确定需要进行多少次的插入排序,再循环依次进行
        for (int i = 1; i < arr.length; i++) {
            //定义待插入数
            int insertVal = arr[i];
            //定义待插入数的前一个数的索引
            int insertIndex = i-1;

            //2.再依次进行插入排序
            // 给insertVal 找到插入的位置
            // insertIndex >= 0  保证插入的位置不越界
            // insertVal < arr[insertIndex] 待插入数 还没有找到插入的位置 就需要 insertIndex 后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;  // insertIndex >= 0 小于零就终止了
            }

            //3.循环完，此时待插入数 比 arr[insertIndex]大
            if (insertIndex+1 != i) {//判断是否需要赋值，如果本来就应该直接插入到最后，就不用赋值了，因为它原本就在那个位置上
                arr[insertIndex+1] = insertVal;
            }
        }
    }
}
